package com.mrzhou.study.struct.array;

/**
 * 数据结构之<h1>单向队列<h1/>的实现
 *  个人理解的队列:
 *      1). 遵循先进先出的规则,
 *      2). 在数组队列中, 元素应从数组尾部指针插入, 从头部指针出
 *      3). 取元素时,应直接从头部指针获取, 添加元素时, 应在尾部指针+1位置插入元素
 *      4). 当队列的头部指针和尾部指针再次重合时, 表示队列中的元素已提取完毕; 可以回收队列的内存空间了
 */
public class QueueSingly<T> {

    private Object[] queue ; // 队列
    private int maxSize ; // 队列的最大上限
    private int rear; // 尾部指针, 也就是数组的下标, 添加元素时使用
    private int front; // 头部指针, 取出元素时使用

    public QueueSingly() {
        super();
        this.maxSize = 20;
        this.queue = new Object[maxSize];
        this.front = -1;
        this.rear = -1;
    }

    public QueueSingly(int size) {
        super();
        this.maxSize = size;
        this.queue = (T[]) new Object[size];
        this.front = -1;
        this.rear = -1;
    }

    public void add(T t) throws Exception {
        rear++;
        if(this.isFull()) {
            throw new Exception("队列已到达最大上限MaxSize: " + queue.length);
        }
        queue[rear] = t;
    }

    /**
     * 从队列中取数据, 个人实现, 这里产生一个疑问, 当队列数组保存的到达最大上限, 但从队列中获取元素
     * 步骤:
     *      头部指针加一;
     * @return
     */
    public T get() throws Exception {
        front++; // 头部指针
        if(this.isEmpty()) {
            throw new Exception("队列为空");
        }
        return (T) queue[front];
    }

    public boolean isEmpty() {
        return front ==  rear;
    }

    public boolean isFull() {
        return front == maxSize -1;
    }

    public String toString() {
        StringBuffer sb = new StringBuffer("[");
        for(int i = 0; i < queue.length; i++) {
            if(i == queue.length -1) {
                sb.append(queue[i]);
            } else {
                sb.append(queue[i] + ", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) throws Exception {
        QueueSingly<String> queue = new QueueSingly<>();
        for(int i =0; i < 20; i++) {
            queue.add("" + i);
        }
        System.out.println();
        for(int i = 0; i < 20; i++) {
            System.out.printf("从队列中取的数据: %s\t\n", queue.get());
        }
        System.out.println();
    }

}
